from typing import List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        res = ListNode()
        temp = res

        index = 0
        while list1 != None and list2 != None:
            if index < a:
                temp.next = list1
                list1 = list1.next
                temp = temp.next

            elif a <= index <= b:
                index = b
                temp.next = list2

                for i in range(a, b+1):
                    list1 = list1.next

                while True:
                    if list2.next == None:
                        temp = list2
                        break
                    list2 = list2.next

            elif index > b:
                temp.next = list1
                list1 = list1.next
                temp = temp.next

            index += 1

        return res.next

    def mergeInBetween2(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        one = list1
        for _ in range(a-1):
            one = one.next
        two = one
        for _ in range(a, b+1):
            two = two.next
        one.next = list2
        while list2.next:
            list2 = list2.next
        list2.next = two.next

        return list1


def gen_list(arr: List[int]) -> ListNode:
    root = ListNode()
    temp = root
    for n in arr:
        inner = ListNode(n)
        temp.next = inner
        temp = inner
    return root.next


nodes = Solution().mergeInBetween2(gen_list([0,1,2,3,4,5,6]), 2, 5, gen_list(
    [1000000,1000001,1000002,1000003,1000004]))
while nodes != None:
    print(nodes.val, end=", ")
    nodes = nodes.next
